package Backtracking;

import java.util.ArrayList;
import java.util.List;

public class _93_RestoreIPAddresses {
    List<String> res;
    String s;
    int len;
    public List<String> restoreIpAddresses(String s) {
        this.res = new ArrayList<>();
        this.s = s;
        this.len = s.length() - 1;
        bp(new ArrayList<>(), 0, "");
        return res;
    }

    //this method can only initial the ip within 255, can not judge the 0
    public void bp(List<String> addrs, int pos, String temp) {
        if (addrs.size() > 4 || pos > len || (!temp.equals("") && Integer.parseInt(temp) > 255)) {
            return;
        } else {
                String word = temp + s.charAt(pos);
                if (Integer.parseInt(word) <= 255) {
                    List<String> tpa = new ArrayList<>(addrs);
                    bp(tpa, pos + 1, word);
                    List<String> tpa2 = new ArrayList<>(addrs);
                    tpa2.add(word);
                    if (tpa2.size() == 4 && pos == len) {
                        String ip = "";
                        boolean ctzero = false;
                        for (String addr : tpa2) {
                            ip += addr + ".";
                            if (addr.length()>1 && addr.charAt(0) == '0') {
                                ctzero = true;
                                break;
                            }
                        }
                        if (!ctzero) {
                            res.add(ip.substring(0, ip.length() - 1));
                        }
                    } else {
                        bp(tpa2, pos + 1, "");
                    }
             }
        }
    }

}
